/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) {
            return;
        }
        while (root) {
            TreeLinkNode *newRoot = NULL;
            TreeLinkNode *cur = root;

            while (cur) {
                TreeLinkNode *sibling = NULL;
                TreeLinkNode *nextNode = cur->next;
                while (nextNode && nextNode->left == NULL && nextNode->right == NULL) {
                    nextNode = nextNode->next;
                }
                if (nextNode) {
                    sibling = nextNode->left ? nextNode->left : nextNode->right;
                }
                if (cur->left) {
                    if (newRoot == NULL) {
                        newRoot = cur->left;
                    }
                    if (cur->right) {
                        cur->left->next = cur->right;
                    } else {
                        cur->left->next = sibling;
                    }

                }
                if (cur->right) {
                    if (newRoot == NULL) {
                        newRoot = cur->right;
                    }
                    cur->right->next = sibling;
                }
                cur = nextNode;
            }
            root = newRoot;
        }
    }
};
